﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Schemes;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Searching
{
    public class BinarySearchProblem<T> : IDecreaseAndConquerProblem<int>
    {
        private readonly IList<T> _list;
        private readonly T _elem;
        private readonly int _i;
        private readonly int _k;
        private readonly Comparison<T> _comparison;

        public BinarySearchProblem(IList<T> list, T elem,int i = 0, int k = -1, Comparison<T> comparison = null)
        {
            _list = list;
            _elem = elem;
            _i = i;
            _k = k > 0 ? k : list.Count;
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        #region Implementation of IDecreaseAndConquerProblem<int>

        public bool IsSimple
        {
            get { return _k - _i <= 1; }
        }

        public int TrivialSolution()
        {
            return _k == _i || _comparison(_elem,_list[_i]) != 0  ? -1 : _i;
        }

        public IDecreaseAndConquerProblem<int> Decrease()
        {
            var pivot =
                (_i + _k)/2;
            if ( _comparison(_elem,_list[pivot]) < 0 )
            {
                return new BinarySearchProblem<T>(_list, _elem, _i, pivot, _comparison);
            }
            return new BinarySearchProblem<T>(_list, _elem, pivot, _k, _comparison);
        }

        public int Process(int solution)
        {
            return solution;
        }

        #endregion
    }
}
